<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-us" lang="en-us">
<head>
  <link href="//gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta name="generator" content="Hugo 0.68.3" />

  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">

  <title>python数据结构----数组 &middot; 我的博客</title>

  
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/print.css" media="print">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/poole.css">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/syntax.css">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/hyde.css">
    <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Abril+Fatface|PT+Sans:400,400i,700">


  
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/apple-touch-icon-144-precomposed.png">
  <link rel="shortcut icon" href="/favicon.png">

  
  
</head>

  <body class="theme-base-0b ">
  <aside class="sidebar">
  <div class="container sidebar-sticky">
    <div class="sidebar-about">
      <a href="/my_technology_blog/"><h1>我的博客</h1></a>
      <p class="lead">
       杨博的博客 
      </p>
    </div>

    <nav>
      <ul class="sidebar-nav">
        <li><a href="/my_technology_blog/">Home</a> </li>
        
      </ul>
    </nav>

    <p>&copy; 2021. All rights reserved. </p>
  </div>
</aside>

    <main class="content container">
    <div class="post">
  <h1>python数据结构----数组</h1>
  <time datetime=2020-06-09T16:45:05&#43;0800 class="post-date">Tue, Jun 9, 2020</time>
  <p><!-- raw HTML omitted --><strong>1、一维数组</strong><!-- raw HTML omitted --></p>
<p>Array类使用python列表来保存其项，常用的魔法方法包括初始化(<strong>init</strong>)、求其长度(<strong>len</strong>)、字符串表示(<strong>str</strong>)、迭代(<strong>iter</strong>)、获取指定位置的值(<strong>getitem</strong>)、设置指定位置的值(<strong>setitem</strong>)</p>
<p>数组的操作主要有：增加数组的长度、减小数组的长度、在数组中插入新的一项、从数组中删除一项。</p>
<ol>
<li>
<pre><code> 增加数组大小：如果逻辑大小和物理大小相等，此时就要增加物理大小，在时间复杂和空间复杂度中折衷中，我们选择将物理大小调整为原来的两倍，然后创建一个新的数组，并且将旧的数组中的值拷贝到新的数组当中，最后将旧的数组变量重置为新的数组变量。
</code></pre>
</li>
<li>
<pre><code> 减小数组大小：条件为：装载因子要小于预设的值(如0.25)同时现在数组的物理大小要为默认值的两倍以上。装载因子为逻辑大小和物理大小的比值。如果满足条件，将物理大小减少一半，后续步骤和增加数组的步骤一样。
</code></pre>
</li>
<li>
<pre><code> 在数组中插入新的一项：在插入之前要先判断是否有可用空间，其次从数组的末尾开始直至目标位置，将每一项后移一个单元，然后见空余的目标位置填入新的值，最后将逻辑大小加1
</code></pre>
</li>
<li>
<pre><code> 在数组中删除一项：从紧跟目标索引位置之后的位置开始，到数组的逻辑末尾，将每一项都向前移动一位；然后将逻辑大小减1；最后判断是否需要减小数组大小。
</code></pre>
</li>
</ol>
<p>Code:</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Array</span>(object):
    <span style="color:#66d9ef">def</span> __init__(self, capacity, fillValue<span style="color:#f92672">=</span>None):
        self<span style="color:#f92672">.</span>items<span style="color:#f92672">=</span> list()
        <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(capacity):
            self<span style="color:#f92672">.</span>items<span style="color:#f92672">.</span>append(fillValue)

    <span style="color:#66d9ef">def</span> __len__(self):
        <span style="color:#e6db74">&#34;&#34;&#34;len of the array&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> len(self<span style="color:#f92672">.</span>items)

    <span style="color:#66d9ef">def</span> __str__(self):
        <span style="color:#e6db74">&#34;&#34;&#34;string representation of thearray&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> str(self<span style="color:#f92672">.</span>items)

    <span style="color:#66d9ef">def</span> __iter__(self):
        <span style="color:#e6db74">&#34;&#34;&#34;iter of thr array&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> iter(self<span style="color:#f92672">.</span>items)

    <span style="color:#66d9ef">def</span> __getitem__(self, index):
        <span style="color:#e6db74">&#34;&#34;&#34;get item of the array atindex&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>items[index]

    <span style="color:#66d9ef">def</span> __setitem__(self, index, newValue):
        <span style="color:#e6db74">&#34;&#34;&#34;set new value of the array at index&#34;&#34;&#34;</span>
        self<span style="color:#f92672">.</span>items[index]<span style="color:#f92672">=</span> newValue

<span style="color:#66d9ef">def</span> <span style="color:#a6e22e">main</span>():
    DEFAULT_CAPACITY <span style="color:#f92672">=</span> <span style="color:#ae81ff">5</span>
    logicalSize <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>
    a <span style="color:#f92672">=</span> Array(DEFAULT_CAPACITY)
    <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(len(a)):
        a[i] <span style="color:#f92672">=</span> i <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>
        logicalSize <span style="color:#f92672">+=</span> <span style="color:#ae81ff">1</span>
    <span style="color:#66d9ef">print</span>(a)
    <span style="color:#e6db74">&#34;&#34;&#34;
</span><span style="color:#e6db74">    Increase size of array:
</span><span style="color:#e6db74">    now logical equal to default capacity
</span><span style="color:#e6db74">    so if you want to add item into array
</span><span style="color:#e6db74">    you should increase capacity of array
</span><span style="color:#e6db74">    &#34;&#34;&#34;</span>
    <span style="color:#66d9ef">if</span> logicalSize<span style="color:#f92672">==</span> DEFAULT_CAPACITY:
        temp <span style="color:#f92672">=</span> Array(len(a) <span style="color:#f92672">*</span> <span style="color:#ae81ff">2</span>)             <span style="color:#75715e"># create a new Array</span>
        <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(logicalSize):
            temp[i] <span style="color:#f92672">=</span> a[i]                   <span style="color:#75715e"># copy data from the old</span>
        a <span style="color:#f92672">=</span> temp
    <span style="color:#66d9ef">print</span>(a)

    <span style="color:#e6db74">&#34;&#34;&#34;
</span><span style="color:#e6db74">    Insert an item into  array
</span><span style="color:#e6db74">    first, check out the logical size ofarray
</span><span style="color:#e6db74">    second, remove item until targetindex
</span><span style="color:#e6db74">    third, set value at index
</span><span style="color:#e6db74">    last, logical size add 1
</span><span style="color:#e6db74">    &#34;&#34;&#34;</span>
    targetIndex<span style="color:#f92672">=</span> <span style="color:#ae81ff">3</span>
    newValue <span style="color:#f92672">=</span> <span style="color:#ae81ff">6</span>
    <span style="color:#66d9ef">if</span> logicalSize<span style="color:#f92672">&lt;</span> len(a):
        <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(logicalSize, targetIndex, <span style="color:#f92672">-</span><span style="color:#ae81ff">1</span>):
            a[i] <span style="color:#f92672">=</span> a[i<span style="color:#f92672">-</span><span style="color:#ae81ff">1</span>]
        a[targetIndex] <span style="color:#f92672">=</span> newValue
        logicalSize <span style="color:#f92672">+=</span> <span style="color:#ae81ff">1</span>
    <span style="color:#75715e"># elif: firstly Increase size of array, secondly run theprevious step</span>
    <span style="color:#66d9ef">print</span>(a)

    <span style="color:#e6db74">&#34;&#34;&#34;
</span><span style="color:#e6db74">    Delete item in array at index
</span><span style="color:#e6db74">    first, remove item
</span><span style="color:#e6db74">    second. logical size sub 1
</span><span style="color:#e6db74">    third, check out the load factor
</span><span style="color:#e6db74">    &#34;&#34;&#34;</span>
    targetIndex <span style="color:#f92672">=</span> <span style="color:#ae81ff">4</span>
    <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(targetIndex, logicalSize):
        a[i] <span style="color:#f92672">=</span> a[i<span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>]
    logicalSize <span style="color:#f92672">-=</span> <span style="color:#ae81ff">1</span>
    <span style="color:#66d9ef">print</span>(a)

    <span style="color:#75715e"># in order to illustrate the decrease size of array, we delete some items</span>
    targetIndex <span style="color:#f92672">=</span> <span style="color:#ae81ff">1</span>
    <span style="color:#66d9ef">for</span> j <span style="color:#f92672">in</span> range(<span style="color:#ae81ff">3</span>):
        <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(targetIndex, logicalSize):
            a[i] <span style="color:#f92672">=</span> a[i<span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>]
        logicalSize <span style="color:#f92672">-=</span> <span style="color:#ae81ff">1</span>
    <span style="color:#66d9ef">print</span>(a)

    <span style="color:#e6db74">&#34;&#34;&#34;
</span><span style="color:#e6db74">    Decrease size of array
</span><span style="color:#e6db74">    first, judge the condition, create anew array
</span><span style="color:#e6db74">    second, copy data from old array tonew
</span><span style="color:#e6db74">    third, assignment
</span><span style="color:#e6db74">    &#34;&#34;&#34;</span>
    <span style="color:#66d9ef">if</span> logicalSize<span style="color:#f92672">&lt;=</span> len(a)<span style="color:#f92672">//</span><span style="color:#ae81ff">4</span> <span style="color:#f92672">and</span> len(a) <span style="color:#f92672">&gt;=</span> DEFAULT_CAPACITY <span style="color:#f92672">*</span> <span style="color:#ae81ff">2</span>:
        temp <span style="color:#f92672">=</span> Array(len(a) <span style="color:#f92672">//</span> <span style="color:#ae81ff">2</span>)
        <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(logicalSize):
            temp[i] <span style="color:#f92672">=</span> a[i]
        a <span style="color:#f92672">=</span> temp
    <span style="color:#66d9ef">print</span>(a)

<span style="color:#66d9ef">if</span> __name__ <span style="color:#f92672">==</span> <span style="color:#e6db74">&#34;__main__&#34;</span>:
    main()
</code></pre></div><p><!-- raw HTML omitted --><strong>1、二维数组</strong><!-- raw HTML omitted --></p>
<p>要创建一个Grid(网格，也值二维数组)对象，可以以3个参数来运行Grid构造方法，即高度、宽度、填充值。需要有初始化函数，获取二维数组的高度和宽度，以及获取索引位置的值，以及打印数组等函数。</p>
<p>code:</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Grid</span>(object):
    <span style="color:#e6db74">&#34;&#34;&#34;representation a two dimensional array&#34;&#34;&#34;</span>
    <span style="color:#66d9ef">def</span> __init__(self, rows, cols, fillValue<span style="color:#f92672">=</span>None):
        self<span style="color:#f92672">.</span>data <span style="color:#f92672">=</span> Array(rows)
        <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(rows):
            self<span style="color:#f92672">.</span>data[i] <span style="color:#f92672">=</span> Array(cols, fillValue)

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">getHeight</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34; return the number of cols &#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> len(self<span style="color:#f92672">.</span>data)

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">getWidth</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;return the number of rows&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> len(self<span style="color:#f92672">.</span>data[<span style="color:#ae81ff">0</span>])

    <span style="color:#66d9ef">def</span> __getitem__(self, index):
        <span style="color:#e6db74">&#34;&#34;&#34;support two-dimensional indexing with [row][col]&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>data[index]

    <span style="color:#66d9ef">def</span> __str__(self):
        <span style="color:#e6db74">&#34;&#34;&#34;return a string representation of the grid&#34;&#34;&#34;</span>
        result <span style="color:#f92672">=</span> <span style="color:#e6db74">&#34;&#34;</span>
        <span style="color:#66d9ef">for</span> row <span style="color:#f92672">in</span> range(self<span style="color:#f92672">.</span>getHeight()):
            <span style="color:#66d9ef">for</span> col <span style="color:#f92672">in</span> range(self<span style="color:#f92672">.</span>getWidth()):
                result <span style="color:#f92672">+=</span> str(self<span style="color:#f92672">.</span>data[row][col]) <span style="color:#f92672">+</span> <span style="color:#e6db74">&#39; &#39;</span>
            result <span style="color:#f92672">+=</span> <span style="color:#e6db74">&#34;</span><span style="color:#ae81ff">\n</span><span style="color:#e6db74">&#34;</span>
        <span style="color:#66d9ef">return</span> result
</code></pre></div><p><!-- raw HTML omitted --><strong>1、三维数组</strong><!-- raw HTML omitted --></p>
<p>可以将三维数组可视化的表示为：一个盒子中装满了较小的盒子，小盒子按照行和列整齐的堆叠，在创建该数组的时候，给定它的深度、高度和宽度，所以三维数组可由一维数组和二维数组共同组成。</p>
<p>Code:</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">lass threeDimensionalArray(object):
    <span style="color:#e6db74">&#34;&#34;&#34;representation three dimensional array&#34;&#34;&#34;</span>
    <span style="color:#66d9ef">def</span> __init__(self, depth, row, col, fillValue<span style="color:#f92672">=</span>None):
        self<span style="color:#f92672">.</span>data <span style="color:#f92672">=</span> Array(depth)
        <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(depth):
            self<span style="color:#f92672">.</span>data[i] <span style="color:#f92672">=</span> Grid(row, col, fillValue)

    <span style="color:#66d9ef">def</span> __getitem__(self, index):
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>data[index]

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">getDepth</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;return the depth of three dimensional array&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> len(self<span style="color:#f92672">.</span>data)

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">getHeight</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;return the row of three dimensional array&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>data[<span style="color:#ae81ff">0</span>]<span style="color:#f92672">.</span>getHeight()

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">getWidth</span>(self):
        <span style="color:#e6db74">&#34;&#34;&#34;return the col of three dimensional array&#34;&#34;&#34;</span>
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>data[<span style="color:#ae81ff">0</span>]<span style="color:#f92672">.</span>getWidth()
</code></pre></div>
</div>


    </main>

    
  </body>
</html>
